Safety Verification and Control for Collision Avoidance at Road Intersections

摘要

This paper presents the design of a supervisory algorithm that monitorssafety at road intersections and overrides drivers with a safe input whennecessary. The design of the supervisor consists of two parts: safetyverification and control design. Safety verification is the problem todetermine if vehicles will be able to cross the intersection without collidingwith current drivers' inputs. We translate this safety verification probleminto a jobshop scheduling problem, which minimizes the maximum lateness andevaluates if the optimal cost is zero. The zero optimal cost corresponds to thecase in which all vehicles can cross each conflict area without collisions.Computing the optimal cost requires solving a Mixed Integer NonlinearProgramming (MINLP) problem due to the nonlinear second-order dynamics of thevehicles. We therefore estimate this optimal cost by formulating two relatedMixed Integer Linear Programming (MILP) problems that assume simpler vehicledynamics. We prove that these two MILP problems yield lower and upper bounds ofthe optimal cost. We also quantify the worst case approximation errors of theseMILP problems. We design the supervisor to override the vehicles with a safecontrol input if the MILP problem that computes the upper bound yields apositive optimal cost. We theoretically demonstrate that the supervisor keepsthe intersection safe and is non-blocking. Computer simulations furthervalidate that the algorithms can run in real time for problems of realisticsize.